#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n);
        ugly[0] = {1};
        int p[3] = {0, 0, 0};
        for (int i = 1; i < n ; i++) {
            int n1, n2, n3;
            n1 = ugly[p[0]] * 2;
            n2 = ugly[p[1]] * 3;
            n3 = ugly[p[2]] * 5;
            int min_val = min(n1, min(n2, n3));
            if (min_val == n1) {
                p[0]++;
            }
            if (min_val == n2) {
                p[1]++;
            }
            if (min_val == n3) {
                p[2]++;
            }
            ugly[i] = min_val;
        }
        return ugly.back();
    }
};

int main() {
    Solution solution;
    int output = solution.nthUglyNumber(10);
    cout << output << endl;
    return 0;
}